\chapter{Especificação}
\label{cap:spec}

Neste capítulo especificaremos os quadros que representam os formatos das mensagens
(\textit{tokens} e pacotes de dados), temporizadores e diagramas da implementação
da ``prova de conceito''.

\section{Especificação de quadros de \textit{tokens}}

%Cada campo de um determinado quadro é representado em \textit{bytes} de acordo com primitivas numéricas em Java.
\begin{enumerate}
\item \textit{Token} Normal\\
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
00000001 & RA & DA & SA & NoN & Gen\_Seq & Coord\_Seq & Seq\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{8} & \multicolumn{1}{c}{8} & \multicolumn{1}{c}{8} & \multicolumn{1}{c}{8}\\
\end{tabular}\\

Permite ao nó detentor usar os recursos disponíveis no anel com exclusividade.

\item \textit{Token} de eleição\\
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
00000010 & RA & DA & SA & MAX\_POWER & MAX\_ID & participantes\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{8} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{8}\\
\end{tabular}\\

Permite eleger proprietário ou coordenador de um anel. O nó que contém ID igual a MAX\_ID é eleito proprietário
ou coordenador.

\item \textit{Token} de aviso de proprietário eleito\\
\begin{tabular}{|c|c|c|c|c|c|}
\hline
00000011 & RA & DA & SA & ELECTED\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2}\\
\end{tabular}\\

Passa de nó em nó anunciando que o nó cujo ID é igual a ELECTED, foi eleito proprietário ou coordenador do anel.

\item \textit{Token} de atribuição de predecessor\\
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
00000100 & RA & DA & SA & NoN & Gen\_Seq & Seq\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{8} & \multicolumn{1}{c}{8} & \multicolumn{1}{c}{8}\\
\end{tabular}\\

Permite que o nó com DA possa ser sucessor do nó com SA. É 
usado para inclusão  e saída de um nó em um anel.

\item \textit{Token} de atribuição de sucessor\\
\begin{tabular}{|c|c|c|c|c|}
\hline
00000101 & RA & DA & SA & NS\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2}\\
\end{tabular}\\

Permite que o nó com DA possa ser predecessor do nó com NS (futuro sucessor).É 
usado para inclusão  e saída de um nó em um anel.

\item Pacote de dados\\
\begin{tabular}{|c|c|c|c|c|}
\hline
00000110 & RA & DA & SA & Data\\
\hline
\end{tabular}\\

Representa pacote de dados de camada de aplicação.

\item Pacote de Ack de dados

Resposta a recebimento de pacotes de dados.

\item \textit{Token} Deletado\\
Para evitar que um \textit{token} (em um varal ou anel) seja recuperado, o valor 00000000 é atribuído ao campo FC de um \textit{token}.

\item \textit{Token} de varal\\
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
00000111 & RA & DA & SA & NoN & Gen\_Seq & Seq\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{8} & \multicolumn{1}{c}{8} & \multicolumn{1}{c}{8}\\
\end{tabular}\\

Permite ao nó detentor usar os recursos disponíveis no anel com exclusividade.

\item \textit{Token} de eleição em um varal\\
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
00001000 & RA & DA & SA & MAX\_POWER & MAX\_ID & participantes\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{8} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{8}\\
\end{tabular}\\

Permite eleger um novo proprietário de varal e passar de nó em nó até voltar ao nó que o gerou.

\item \textit{Token} de aviso de proprietário eleito em um varal\\
\begin{tabular}{|c|c|c|c|c|c|}
\hline
00001001 & RA & DA & SA & ELECTED\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2}\\
\end{tabular}\\

Passa de nó em nó anunciando que o nó cujo ID igual a ELECTED, foi eleito proprietário do varal.

\item \textit{Token} de atribuição de predecessor em um varal\\
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
00001010 & RA & DA & SA & NoN & Gen\_Seq & Seq\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{8} & \multicolumn{1}{c}{8} & \multicolumn{1}{c}{8}\\
\end{tabular}\\

Permite que o nó com DA possa ser sucessor do nó com SA. É 
usado para inclusão  e saída de um nó em um varal.

\item \textit{Token} de atribuição de sucessor em um varal\\
\begin{tabular}{|c|c|c|c|c|}
\hline
00001011 & RA & DA & SA & NS\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2}\\
\end{tabular}\\

Permite que o nó com DA possa ser predecessor do nó com NS (futuro sucessor). É 
usado para inclusão  e saída de um nó em um varal.

\item Pacote de dados em um varal\\
\begin{tabular}{|c|c|c|c|c|}
\hline
00001100 & RA & DA & SA & Data\\
\hline
\end{tabular}\\

Representa pacote de dados em um varal.

\item \textit{Token} de aviso de entrada\\
\begin{tabular}{|c|c|c|c|c|}
\hline
00001101 & RA & DA & SA & ID\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2}\\
\end{tabular}\\

Este \textit{token} é utilizado para avisar que o nó N acabou de entrar no anel cujo endereço é RA. Ele transita de 
sucessor em sucessor até o predecessor do nó com identificador ID.

\item \textit{Token} de aviso de saída\\
\begin{tabular}{|c|c|c|c|c|}
\hline
00001110 & RA & DA & SA & ID\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2}\\
\end{tabular}\\

Este \textit{token} é utilizado para avisar que o nó que contém identificador igual a ID saiu do anel cujo endereço é RA. Ele transita de 
sucessor em sucessor até o predecessor do nó com identificador ID.

\item \textit{Token} de reentrada\\
\begin{tabular}{|c|c|c|c|c|}
\hline
00001111 & RA & DA & SA & ID\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2}\\
\end{tabular}\\

Este \textit{token} é utilizado quando um nó quer enviar ID dele para o sucessor. Sempre que
houver queda inesperada em um anel, este \textit{token} é enviado e recebido entre os 
nós restantes no anel.

\item \textit{Token} de solicitação de entrada em um anel\\
\begin{tabular}{|c|c|c|c|}
\hline
00010000 & RA & Br. & SA\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2}\\
\end{tabular}\\

Um nó usa este token para solicitar entrada em um anel. O campo RA
é ID desse nó, se esse nó chegou a formar um anel unitário. Senão, RA é um campo com valor inválido.

\item \textit{Token} de solicitação de entrada em um varal\\
\begin{tabular}{|c|c|c|c|}
\hline
00010001 & RA & Br. & SA\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2}\\
\end{tabular}\\

Um nó usa este token para solicitar entrada em um varal. O campo RA
é RA do anel a qual o nó faz parte.

\item \textit{Token} de resposta a solicitação de entrada em um anel\\
\begin{tabular}{|c|c|c|c|}
\hline
00010010 & DA & SA & MY\_SUCC\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2}\\
\end{tabular}\\

Esse token é enviado em resposta para um nó que solicite entrada em um anel.

\item \textit{Token} de resposta a solicitação de entrada em um varal\\
\begin{tabular}{|c|c|c|c|}
\hline
00010101 & DA & SA & MY\_SUCC\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2}\\
\end{tabular}\\

Esse token é enviado em resposta para um nó que solicite entrada em um varal.

\item \textit{Token} de alerta de saída de um coordenador\\
\begin{tabular}{|c|c|c|c|c|c|}
\hline
00010110 & RA & Br. & SA & PRED & SUCC\\
\hline
\multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{2}\\
\end{tabular}\\

O coordenador cessante do anel RA faz um \textit{broadcast} avisando que vai sair.
\end{enumerate}


\chapter{Os problemas de terminal oculto e terminal exposto}
\label{ape:hiddenexpost}

Neste capítulo introduzimos dois dos notáveis problemas em redes de natureza sem fio.

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{hidden-node-img.pdf}
\caption{O problema de terminal oculto}
\label{fig:hiddennode}
\end{figure}

O protocolo MAC CSMA (\textit{Carrier Sense Multiple Access} - vide Kleinrock, Tobagi 1975) que é utilizado em tecnologias 802.11, é simples e
intuitivo ~\cite{toumpis}. Porém, este protocolo sofre do problema de terminal (nó) oculto e do problema de terminal exposto.

Para explicar o problema de terminal oculto, consideremos a figura ~\ref{fig:hiddennode}. Os terminais 1 e 3 não escutam as transmissões entre si.
Se ambos utilizam CSMA e transmitirem sinais para o terminal 2 simultaneamente, poderá ocorrem colisão de sinais, e estes se auto-destruírem.

\begin{figure}[!hbtp]
\centering
\includegraphics[scale=0.4]{exposed-node-img.pdf}
\caption{O problema de terminal exposto}
\label{fig:exposednode}
\end{figure}

No problema de terminal exposto um terminal não transmite sinais se ele perceber que algum terminal na sua
vizinhança está transmitindo. Para explicar melhor o problema de terminal exposto, vamos considerar a figura \ref{fig:exposednode}. Consideremos que
o terminal 3 está usando o CSMA como protocolo MAC, e o terminal 2 está transmitindo pacotes para o terminal 1. Como terminal 2 escuta as 
transmissões do terminal 3 e vice-versa. Se o terminal 3 tiver pacotes para o terminal 4, então enquanto o terminal 2 transmite para o terminal 1, 
o terminal 3 não transmitirá pacotes para o nó 4. Consequentemente, o terminal 3 vai provocar disperdício de largura de banda.

%FALAR DE SOLUÇÕES PARA ESSES DOIS PROBLEMAS

\chapter{Implementação em C++}
\label{ape:sourcecode}
\textbf{Arquivo wtrp.h}
\lstinputlisting{/home/adroaldo/ns-allinone-2.35/ns-2.35/manet-trp/wtrp.h}
\textbf{Arquivo wtrp.cc}
\lstinputlisting{/home/adroaldo/ns-allinone-2.35/ns-2.35/manet-trp/wtrp.cc}
\textbf{Arquivo wtrp\_packet.h}
\lstinputlisting{/home/adroaldo/ns-allinone-2.35/ns-2.35/manet-trp/wtrp_packet.h}
\textbf{Arquivo ringutils.h}
\lstinputlisting{/home/adroaldo/ns-allinone-2.35/ns-2.35/manet-trp/ringutils.h}
\textbf{Arquivo ringutils.cc}
\lstinputlisting{/home/adroaldo/ns-allinone-2.35/ns-2.35/manet-trp/ringutils.cc}
\textbf{Arquivo utils-constants.h}
\lstinputlisting{/home/adroaldo/ns-allinone-2.35/ns-2.35/manet-trp/utils-constants.h}
\textbf{Arquivo packet\_queue.h}
\lstinputlisting{/home/adroaldo/ns-allinone-2.35/ns-2.35/manet-trp/packet_queue.cc}
\textbf{Arquivo packet\_queue.cc}
\lstinputlisting{/home/adroaldo/ns-allinone-2.35/ns-2.35/manet-trp/packet_queue.h}